/*
    6. Write a C program to sort numbers using heap algorithm(MAX heap). 
    A sorting algorithm that works by first organizing the data to be 
    sorted into a special type of binary tree called a heap.
*/

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void maxheap(int a[], int len)
{
    int i, l, r;
    for(i = 0; i < len; i++){
        l = 2 * i + 1;
        r = 2 * i + 2;
        if(l < len){
            if(a[i] < a[l]){
                swap(&a[i], &a[l]);
            }
        }
        if(r < len){
            if(a[i] < a[r]){
                swap(&a[i], &a[r]);
            }
        }         
    }
}

void maxheapify(int a[], int head, int end)
{
    int i, l, r;
    for(i = head; i <= end; i++){
        l = 2 * i + 1;
        r = l + 1;
        if(l <= end && r <= end){
            if(a[l] < a[r]){
                swap(&a[l], &a[r]);
            }
        }
        if(l <= end){
            if(a[i] < a[l]){
                swap(&a[i], &a[l]);
            }
        }
    }
}

void heapsort(int a[], int len)
{
    int i, j;
    for(j = len - 1; j >= 0; j--){
        /*max root*/
        for(i = j / 2 - 1; i >= 0; i--){ // right node (r = 2 * father + 2 < len) => last father is (len/2 - 1)  
            maxheapify(a, i, j);
        }
        /*swap max to last */
        swap(&a[0], &a[j]);
    }
}

void printarray(int a[], int len)
{
    int i;
    for(i = 0; i < len; i++){
        printf("%d, ", a[i]);
    }
    printf("\n");
}

int main(void)
{
    int i, len;
    printf("Input the size of array : ");
    scanf("%d", &len);
    int *a = (int *)malloc(len * sizeof(int));
    printf("Input value into array : \n");
    for(i = 0; i < len; i++){
        scanf("%d", &a[i]);
    }
    heapsort(a, len);
    printarray(a, len);

    return 0;
}